import java.util.*;

/**
 * <a href="https://leetcode.cn/studyplan/programming-skills/">LeeCode 编程基础 0 到 1</a>
 */
public class BasicPracticeMethod {
    /**
     * 1768. 交替合并字符串
     * @description: 请你从 word1 开始，通过交替添加字母来合并字符串。
     *      如果一个字符串比另一个字符串长，就将多出来的字母追加到合并后字符串的末尾。
     * @return 合并后的字符串
     */
    public static String mergeAlternately(String word1, String word2) {
        StringBuilder resultBuilder = new StringBuilder();
        int shorter = Math.min(word1.length(), word2.length());
        for(int i=0;i<shorter;i++){
            resultBuilder.append(word1.charAt(i)).append(word2.charAt(i));
        }
        if(word1.length()<word2.length()){
            resultBuilder.append(word2.substring(shorter));
        }
        if(word1.length()>word2.length()){
            resultBuilder.append(word1.substring(shorter));
        }

        return resultBuilder.toString();
    }

    /**
     * 389. 找不同
     * @description: 给定两个字符串 s 和 t ，它们只包含小写字母。
     * 字符串 t 由字符串 s 随机重排，然后在随机位置添加一个字母。
     * 请找出在 t 中被添加的字母。
     * @return
     */
    public static char findTheDifference(String s, String t) {
        //方法1：list加减
        List<Character> list = new ArrayList<>();
        for(Character c : t.toCharArray()){
            list.add(c);
        }
        for(Character c: s.toCharArray()){
            list.remove(c);
        }
//        return list.get(0);

        //方法2：ASCII码加减(空间复杂度O(1)，推荐)
        //将char强制转为int，得到的是它的ascii码；int直接加减char，也是在加减char对应的ascii码
        int result = 0;
        for(char c: t.toCharArray()){
            result += c;
        }
        for(char c: s.toCharArray()){
            result -= c;
        }
        System.out.println((char)result);
        return (char)result;
    }

    /**
     * 28. 找出字符串中第一个匹配项的下标
     */
    public int strStr(String haystack, String needle) {
        return haystack.indexOf(needle);
    }

    /**
     * 242. 有效的字母异位词
     * @description: 给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词(内容相同顺序不同)。
     */
    public boolean isAnagram(String s, String t) {
        //方法一：list加减
        if(s.length()!=t.length()){
            return false;
        }
        List<Character> list = new ArrayList<>();
        for(Character c: s.toCharArray()){
            list.add(c);
        }
        for(Character c: t.toCharArray()){
            if(!list.contains(c)){
                return false;
            }
            list.remove(c);
        }
//        return true;

        //方法2：将s、t转为Array，然后sort，判断排序后的Array是否相同(耗时更短)
        char[] sa = s.toCharArray();
        char[] ta = t.toCharArray();
        Arrays.sort(sa);
        Arrays.sort(ta);

        return Arrays.equals(sa, ta);
    }

    /**
     * 283. 移动零
     * @description: 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
     * 请注意 ，必须在不复制数组的情况下原地对数组进行操作。
     */
    public void moveZeroes(int[] nums) {
        //方法1：
        for(int i=0; i<nums.length;i++){
            if(nums[i]==0){
                for(int j=i;j<nums.length;j++){
                    if(nums[j]!=0){
                        nums[i] = nums[j];
                        nums[j] = 0;
                        break;
                    }
                }
            }
        }
        //方法2：双指针，耗时更短
        int left = 0, right = 0;
        int temp;
        while(right<nums.length){
            if(nums[right]!=0){
                temp = nums[left];
                nums[left]=nums[right];
                nums[right]=temp;
                left++;
            }
            right++;
        }
    }
    public static int[] plusOne(int[] digits) {
        int num = digits[digits.length-1]/10;//位数
        digits[digits.length-1] = digits[digits.length-1]+1;
        int[] result = digits;
        if(digits[digits.length-1]/10>num){
            result[result.length-1] -= 10*(num+1);
            result = plusOne(digits, digits.length-2);
        }
        return result;
    }
    public static int[] plusOne(int[] digits, int index){
        if(index<0){
            int[] result = new int[digits.length+1];
            result[0]=1;
            for(int i=0;i<digits.length;i++){
                result[i+1] = digits[i];
            }
            return result;
        }
        int num = digits[index]/10;//位数
        digits[index] = digits[index]+1;
        if(digits[index]/10>num){
            digits[index]-=10*(num+1);
            digits = plusOne(digits, index-1);
        }
        return digits;
    }

    /**
     * 204. 计数质数
     * @description: 给定整数 n ，返回 所有小于非负整数 n 的质数的数量 。
     */
    public int countPrimes(int n) {
        //方法一：枚举/暴力法（大数会超时）
//        if(n<2){
//            return 0;
//        } else if (n==2) {
//            return 1;
//        }else{
//            int count = 1;
//            for (int i = 3; i < n; i+=2) {
//                if(isPrime(i)){
//                    count++;
//                }
//            }
//            return count;
//        }

        //方法2：埃氏筛
        int[] arr = new int[n];
        int count = 0;
        for(int i = 2; i<n; i++){
            if(arr[i]==1){
                continue;
            }
            //从j=2开始，将j的所有倍数都记为合数
            for(int j=2; j*i<n; j++){
                arr[j*i]=1;
            }
            count++;
        }
        return count;
    }
    /**
     * 判断n是否为质数
     */
    public boolean isPrime(int n){
        //Point: i的取值范围可以压缩到根号i，节省时间
        for(int i = 2; i*i<n;i++){
            if(n%i==0){
                return false;
            }
        }
        return true;
    }

    /**
     * 459. 重复的子字符串
     * @description: 给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。
     */
    public boolean repeatedSubstringPattern(String s) {
        //如果是，那么将第一位移到最后一位也一定是
        //s+s后将第一位移到最后一位，也一定包含s
        return (s + s).substring(1, 2 * s.length() - 1).contains(s);
    }

    /**
     * 1822. 数组元素积的符号
     * @description: 给你一个整数数组 nums 。令 product 为数组 nums 中所有元素值的乘积的正负（-1，0，1）。
     */
    public int arraySign(int[] nums) {
        int result = 1;
        for(int n: nums){
            if(n == 0){
                return 0;
            }
            if(n < 0){
                result = -result;
            }
        }
        return result;
    }

    /**
     * 1502. 判断能否形成等差数列
     * @description: 给你一个数字数组 arr 。
     * 如果可以重新排列数组形成等差数列，请返回 true ；否则，返回 false 。
     */
    public boolean canMakeArithmeticProgression(int[] arr) {
        Arrays.sort(arr);
        int gap = arr[1] - arr[0];
        for (int i = 0; i < arr.length-1; i++) {
            if(arr[i+1]-arr[i]!=gap){
                return false;
            }
        }
        return true;
    }

    /**
     * 896. 单调数列
     * @description: 当给定的数组 nums 是单调数组时返回 true，否则返回 false。
     */
    public boolean isMonotonic(int[] nums) {
        boolean increase = false;
        boolean decrease = false;
        for(int i = 0; i< nums.length-1;i++){
            if((nums[i+1]-nums[i])<0){
                decrease = true;
            } else if (nums[i+1]-nums[i]>0) {
                increase = true;
            }

            if(increase&&decrease){
                return false;
            }
        }
        return true;
    }

    /**
     * 13. 罗马数字转整数
     */
    public int romanToInt(String s) {
        char[] Roman = s.toCharArray();
        int[] Arabic = new int[Roman.length];
        Map<Character, Integer> RomanToArabic = new HashMap<>();
        RomanToArabic.put('I', 1);
        RomanToArabic.put('V', 5);
        RomanToArabic.put('X', 10);
        RomanToArabic.put('L', 50);
        RomanToArabic.put('C', 100);
        RomanToArabic.put('D', 500);
        RomanToArabic.put('M', 1000);
        for(int i=0; i<Roman.length; i++){
            Arabic[i] = RomanToArabic.get(Roman[i]);
        }
        int sum = Arabic[Arabic.length-1];
        for(int i=Arabic.length-2; i>=0; i--){
            if(Arabic[i]<Arabic[i+1]){
                sum-=Arabic[i];
            }else{
                sum+=Arabic[i];
            }
        }
        return sum;
    }

    /**
     * 682. 棒球比赛
     */
    public int calPoints(String[] operations) {
        List<Integer> score = new ArrayList<>();
        for(String str: operations){
            switch (str) {
                case "+":
                    score.add(score.get(score.size()-1)+score.get(score.size()-2));
                    break;
                case "D":
                    score.add(score.get(score.size()-1)*2);
                    break;
                case "C":
                    score.remove(score.size()-1);
                    break;
                default:
                    score.add(Integer.parseInt(str));
            }
        }
        int sum = 0;
        for(int n: score){
            sum+=n;
        }
        return sum;
    }

    /**
     * 657. 机器人能否返回原点
     */
    public boolean judgeCircle(String moves) {
        int x=0,y=0;
        for(char c: moves.toCharArray()){
            switch (c){
                case 'R':
                    x+=1;
                    break;
                case 'L':
                    x-=1;
                    break;
                case 'U':
                    y+=1;
                    break;
                case 'D':
                    y-=1;
                    break;
            }
        }
        return x==0&&y==0;
    }

    /**
     * 1275. 找出井字棋的获胜者
     */
    public String tictactoe(int[][] moves) {
        //创建一个2维数组，用于存储当前棋盘上的棋子，默认值0为未下，1为A子，-1为B子
        int[][] board = new int[3][3];
        for(int i=0;i< moves.length;i++){
            int newRow = moves[i][0];
            int newColumn = moves[i][1];
            //按顺序落子
            if(i%2==0){
                board[newRow][newColumn]=1;
            }else{
                board[newRow][newColumn]=-1;
            }
            //计算行列斜的和，是否为3或-3，如果是，说明已分胜负
            int rowSum = board[newRow][0]+board[newRow][1]+board[newRow][2];
            int colSum = board[0][newColumn]+board[1][newColumn]+board[2][newColumn];
            int lrSum = 0;
            int rlSum = 0;
            if(newRow == newColumn){
                lrSum = board[0][0]+board[1][1]+board[2][2];
            }
            if(newRow+newColumn==2){
                rlSum = board[0][2]+board[1][1]+board[2][0];
            }

            if(rowSum==3||colSum==3||lrSum==3||rlSum==3){
                return "A";
            }
            if(rowSum==-3||colSum==-3||lrSum==-3||rlSum==-3){
                return "B";
            }
        }

        //3x3的棋盘，最多走9步，如果未分胜负，落子数小于9，返回“Pending（游戏未结束）”
        if(moves.length<9){
            return "Pending";
        }
        //返回“Draw（平局）”
        return "Draw";
    }
    /**
     * 1041. 困于环中的机器人
     */
    public boolean isRobotBounded(String instructions) {
        //传入移动规则、当前位置、当前朝向
        return isRobotBounded(instructions, 0, 0, 0);
    }
    public boolean isRobotBounded(String instructions, int nx, int ny, int nDirection){
        int direction = nDirection;
        int x=nx,y=ny;
        //移动一轮
        for(char c: instructions.toCharArray()){
            switch (c){
                case 'R':
                    direction = (direction+1)%4;
                    break;
                case 'L':
                    direction = (direction==0)?4:direction;
                    direction = (direction-1)%4;
                    break;
                case 'G':
                    switch (direction){
                        case 0:
                            y++;
                            break;
                        case 1:
                            x++;
                            break;
                        case 2:
                            y--;
                            break;
                        case 3:
                            x--;
                            break;
                    }
                    break;
            }
        }
        //如果移动完毕后回到原点，说明存在环
        if(x==0&&y==0){
            return true;
        }
        //如果移动完毕后不在原点，且面朝北方，说明不存在环
        if(direction==0){
            return false;
        }
        //再移动一轮看看，直到回到原点、或面朝北方
        return isRobotBounded(instructions, x, y, direction);
    }
    /**
     * 1672. 最富有客户的资产总量
     */
    public int maximumWealth(int[][] accounts) {
        int max = 0;
        for(int[] arr: accounts){
            int temp = 0;
            for(int n: arr){
                temp+=n;
            }
            if(temp>max){
                max=temp;
            }
        }
        return max;
    }

    /**
     * 1572. 矩阵对角线元素的和
     */
    public int diagonalSum(int[][] mat) {
        int sum = 0;
        int num = mat.length-1;
        for (int i = 0; i < mat.length; i++) {
            //左上到右下
            sum += mat[i][i];
            //右上到左下
            sum += mat[i][num-i];
        }
        //去掉算了两次的中央值（如果行数为奇数）
        if(mat.length%2!=0){
            int mid = mat.length/2;
            sum -= mat[mid][mid];
        }
        return sum;
    }

    /**
     * 54. 螺旋矩阵
     * @description: 给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
     */
    public static List<Integer> spiralOrder(int[][] matrix) {
        //传入m*n的矩阵
        int m = matrix[0].length;//列数
        int n = matrix.length;//行数
        //格子数
        int total = m*n;
        //当前位置
        int row=0, col=0;
        //目前是第几圈
        int circle = 1;
        //当前移动方向（0-右；1-下；2-左；3-上）
        int direction = 0;
        List<Integer> result = new ArrayList<>();
        for(int i=0;i<total;i++){
            //将当前位置的数值加入结果集
            result.add(matrix[row][col]);
            //移动
            //判断是否需要转向
            if(direction==0&&col>=m-circle){
                direction = 1;
            }else if(direction==1&&row>=n-circle){
                direction = 2;
            }else if(direction==2&&col<=circle-1){
                direction = 3;
            }else if(direction==3&&row<=circle){
                direction = 0;
                circle++;
            }
            switch (direction){
                case 0:
                    col++;
                    break;
                case 1:
                    row++;
                    break;
                case 2:
                    col--;
                    break;
                case 3:
                    row--;
                    break;
            }
        }
        return result;
    }

    /**
     * 73. 矩阵置零
     * @description: 给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。
     */
    public static void setZeroes(int[][] matrix) {
        //先解决特殊情况（只有1行/只有1列的情况）
        if(matrix.length==1){
            for(int n: matrix[0]){
                if(n==0){
                    Arrays.fill(matrix[0], 0);
                    return;
                }
            }
        }
        if(matrix[0].length==1){
            for(int[] arr: matrix){
                if(arr[0]==0){
                    for(int i=0;i<matrix.length;i++){
                        matrix[i][0]=0;
                    }
                    return;
                }
            }
        }

        //判断第一列是否存在0
        boolean colHasZero = false;
        for(int[] arr: matrix){
            if(arr[0]==0){
                colHasZero=true;
                break;
            }
        }
        //判断第一行是否存在0
        boolean rowHasZero = false;
        for(int n: matrix[0]){
            if(n==0){
                rowHasZero=true;
                break;
            }
        }


        //除了第一行&第一列，判断是否存在0；如果有，则把对应的行列的第一格设为0
        for(int i=1;i<matrix.length;i++){
            for(int j=1;j<matrix[0].length;j++){
                if(matrix[i][j]==0){
                    matrix[i][0]=0;
                    matrix[0][j]=0;
                }
            }
        }
        //判断第一列是否存在0，如果有，则将对应行全部设为0
        for (int i = 1; i < matrix.length; i++) {
            if(matrix[i][0]==0){
                for(int j=1;j<matrix[0].length;j++){
                    matrix[i][j]=0;
                }
            }
        }
        //判断第一行是否存在0，如果有，则将对应列全部设为0
        for (int j = 1; j < matrix[0].length; j++) {
            if(matrix[0][j]==0){
                for(int i=1;i<matrix.length;i++){
                    matrix[i][j]=0;
                }
            }
        }
        //判断左上角是否为0.如果是，则把第一行、第一列都设为0
        if(matrix[0][0]==0){
            for (int i = 0; i < matrix.length; i++) {
                matrix[i][0]=0;
            }
            Arrays.fill(matrix[0], 0);
        }
        //判断第一行、第一列原始是否有0
        if(colHasZero){
            for(int i=0;i<matrix.length;i++){
                matrix[i][0]=0;
            }
        }
        if(rowHasZero){
            Arrays.fill(matrix[0], 0);
        }
    }

    /**
     * 1491. 去掉最低工资和最高工资后的工资平均值
     */
    public double average(int[] salary) {
        Arrays.sort(salary);
        int sum = 0;
        for (int i = 1; i < salary.length-1; i++) {
            sum+=salary[i];
        }
        return ((double)sum)/(salary.length-2);
    }

    /**
     * 860. 柠檬水找零
     */
    public boolean lemonadeChange(int[] bills) {
        //记录手上5元、10元的数量（20元用不上，记不记都可以）
        int[] counts = {0,0};
        for(int income: bills){
            switch (income){
                case 5:
                    counts[0]++;
                    break;
                case 10:
                    if(counts[0]<1){
                        //没有5元可找，返回失败
                        return false;
                    }
                    counts[0]--;//减少1张5元
                    counts[1]++;//增加1张10元
                    break;
                case 20:
                    //优先找10元，因为10元只能在这里消耗掉
                    if(counts[1]>0&&counts[0]>0){
                        counts[1]--;
                        counts[0]--;
//                        counts[2]++;
                        break;
                    }
                    //没有10元，尝试找3张5元
                    if(counts[0]>=3){
                        counts[0]-=3;
//                        counts[2]++;
                        break;
                    }
                    //都不成功，返回失败
                    return false;
            }
        }
        //全部找完，返回成功
        return true;
    }

    /**
     * 976. 三角形的最大周长
     * @description: 给定由一些正数（代表长度）组成的数组 nums ，
     * 返回 由其中三个长度组成的、面积不为零的三角形的最大周长 。
     * 如果不能形成任何面积不为零的三角形，返回 0。
     */
    public int largestPerimeter(int[] nums) {
        Arrays.sort(nums);
        for(int i = nums.length-1;i-2>=0;i--){
            if(nums[i]-nums[i-1]<nums[i-2]){
                return nums[i]+nums[i-1]+nums[i-2];
            }
        }
        return 0;
    }

    /**
     * 1232. 缀点成线
     * @description: 判断数组coordinates中的所有点是否在该坐标系中属于同一条直线上。
     */
    public boolean checkStraightLine(int[][] coordinates) {
        //判断特殊情况（平行于y轴），此时斜率不存在
        if(coordinates[1][0]-coordinates[0][0]==0){
            for(int[] coordinate: coordinates){
                if(coordinate[0]!=coordinates[0][0]){
                    return false;
                }
            }
            return true;
        }

        double k = ((double)coordinates[1][1] - coordinates[0][1]) /(coordinates[1][0]-coordinates[0][0]);
        for(int i=1; i<coordinates.length;i++){
            if(coordinates[i][0]==coordinates[i-1][0]){
                return false;
            }
            double tk = ((double)coordinates[i][1] - coordinates[i-1][1]) /(coordinates[i][0]-coordinates[i-1][0]);
            if(tk!=k){
                return false;
            }
        }
        return true;
    }

    /**
     * 67. 二进制求和
     * @description: 给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。
     */
    public static String addBinary(String a, String b) {
        //注意，两者长度相同时，要保证longer和shorter分别为a和b
        String shorter = a.length()<=b.length()?a:b;
        String longer = b.length()>=a.length()?b:a;
        int pa = shorter.length()-1;
        int pb = longer.length()-1;
        StringBuilder result = new StringBuilder();
        int carry = 0;
        while(pa>=0){
            int va = shorter.charAt(pa)=='1'?1:0;
            int vb = longer.charAt(pb)=='1'?1:0;
            int sum = va+vb+carry;
            switch (sum){
                case 0:
                    result.insert(0, "0");
                    carry = 0;
                    break;
                case 1:
                    result.insert(0, "1");
                    carry = 0;
                    break;
                case 2:
                    result.insert(0, "0");
                    carry = 1;
                    break;
                case 3:
                    result.insert(0, "1");
                    carry = 1;
                    break;
            }
            pa--;
            pb--;
        }
        //短的处理完，可能会遗留1个进一
        while(carry==1&&pb>=0){
            int sum = (longer.charAt(pb)=='1'?1:0)+carry;
            switch (sum){
                case 1:
                    result.insert(0,"1");
                    carry=0;
                    break;
                case 2:
                    result.insert(0,"0");
                    break;
            }
            pb--;
        }
        //如果此时carry还是1，说明已经加到头了，直接在结果前面加上1即可
        if(carry==1){
            result.insert(0,"1");
            return result.toString();
        }
        //否则，将较长的哪一个前面剩下的再加到前面
        result.insert(0,longer.substring(0,pb+1));
        return result.toString();
    }

    /**
     * 50. Pow(x, n)
     * @description: 高效计算x的n次方
     */
    public double myPow(double x, int n) {
        //x的10次方=x的（8+2）次方=x^(2^3)*x^(2^1)
        //10转化为二进制为1010
        //求x的n次方，可以从x^(2^0)开始，不断将其中2的次方数增加
        //即x^2=x*x, x^4=(x^2)*(x^2),x^8=(x^4)*(x^4)
        //同时依据n的二进制字符串从右往左判断，如果是1，则将本次计算结果乘到最终结果即可
        //例如：求x^5，5->101，result=1
        //第一步，求x^(2^0)=x^1=x, 101的右1位为1，result=1*x^1
        //第二步，求x^(2^1)=x^2=x*x，101的右2位为0，result不变，只把x^2保存下来
        //第三步，求x^(2^2)=x^4=(x^2)*(x^2)，101的右3位为1，result=1*x^1*x^4=x^5，得到所需结果

        //先处理特殊情况
        if(x==0){
            return 0;
        }
        if(n==0){
            return 1;
        }
        int sign = 1;//正负标记
        if(n<0){
            sign = -1;
            n=-n;
        }

        String binary = Integer.toBinaryString(n);
        double result = 1;
        //如果binary最后1位为1，先乘1次x，下面就不处理这个了
        if(n%2==1){
            result = x;
        }
        double current = x;
        for (int i = binary.length()-2; i >= 0 ; i--) {
            current = current * current;
            if(binary.charAt(i)=='1'){
                result*=current;
            }
        }
        if(sign==-1){
            result = 1/result;
        }

        return result;
    }

    /**
     * 2610. 转换二维数组
     * @param nums
     * @description 给你一个整数数组 nums 。请你创建一个满足以下条件的二维数组：
     * 二维数组应该 只 包含数组 nums 中的元素。
     * 二维数组中的每一行都包含 不同 的整数。
     * 二维数组的行数应尽可能 少 。
     * 返回结果数组。如果存在多种答案，则返回其中任何一种。
     * 请注意，二维数组的每一行上可以存在不同数量的元素。
     * @return
     */
    public List<List<Integer>> findMatrix(int[] nums) {
        List<Integer> okList = new ArrayList<>();
        List<Integer> leftList = new ArrayList<>();
        List<List<Integer>> resultList = new ArrayList<>();
        for(int i: nums){
            leftList.add(i);
        }
        int pointer = 0;
        while(!leftList.isEmpty()){
            int max = leftList.get(pointer);
            if(!okList.contains(max)){
                okList.add(max);
                leftList.remove(pointer);
            }else{
                pointer = pointer + 1;
            }
            if(pointer == leftList.size()){
                pointer = 0;
                resultList.add(okList);
                okList = new ArrayList<>();
            }
        }
        return resultList;
    }

    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        int tempMax;
        ListNode resultHead, resultTail, currentNode, waitingNode;
        if(list1.val<=list2.val){
            tempMax = list2.val;
            resultHead = new ListNode(list1.val);
            list1 = list1.next;
            currentNode = list1;
            waitingNode = list2;
        }else{
            tempMax = list1.val;
            resultHead = new ListNode(list2.val);
            list2 = list2.next;
            currentNode = list2;
            waitingNode = list1;
        }
        resultTail=resultHead;
        while(currentNode.next!=null){
            if(currentNode.val<=tempMax){
                resultTail.next = currentNode;
                resultTail=resultTail.next;
                currentNode=currentNode.next;
            }else{
                resultTail.next = waitingNode;
                resultTail=resultTail.next;
                waitingNode = currentNode;
                currentNode = resultTail.next;
                tempMax = waitingNode.val;
            }
        }

        return resultHead;
    }
    public static class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    /**
     * 反转链表
     * @param head
     * @return
     */
    public ListNode reverseList(ListNode head) {
        ListNode currentHead = head.next;
        if(currentHead==null){
            return head;
        }
        if(currentHead.next==null){
            currentHead.next=head;
            head.next=null;
        }
        ListNode middle = head;
        ListNode left = head;
        while(currentHead.next!=null){
            middle = currentHead;
            currentHead = currentHead.next;
            middle.next = left;
            left = middle;
        }
        currentHead.next=middle;
        head.next=null;
        return currentHead;
    }

    /**
     *
     * @param l1
     * @param l2
     * @return
     */
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = null, tail = null;
        int a, b, sum;
        ListNode former = new ListNode(0);
        while(l1!=null || l2 !=null){
            if(l1!=null){
                a = l1.val;
                l1 = l1.next;
            }else{
                a=0;
            }
            if(l2!=null){
                b = l2.val;
                l2=l2.next;
            }else{
                b=0;
            }
            sum = a+b;

            if(head==null){
                head = new ListNode(sum%10);
                tail = new ListNode(sum/10);
                head.next=tail;
                continue;
            }
            sum += tail.val;
            tail.next = new ListNode(sum/10);
            tail.val = sum%10;
            former = tail;
            tail = tail.next;
        }
        if(tail.val==0){
            former.next=null;
        }
        return head;
    }

}
